
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1496. -- [NOI2006]千年虫 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1496: [NOI2006]千年虫</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>259 MB<br><span class=green>Submit: </span>64&nbsp;&nbsp;<span class=green>Solved: </span>44<br>[<a href='submitpage.php?id=1496'>Submit</a>][<a href='problemstatus.php?id=1496'>Status</a>][<a href='bbs.php?id=1496'>Discuss</a>]</center><h2>Description</h2><div class=content>千年虫是远古时代的生物，时隔几千万年，千年虫早已从地球上销声匿迹，人们对其知之甚少。考古生物学家最近开始对其有了兴趣，因为一批珍贵的千年虫化石被发现，这些化石保留了千年虫近乎完整的形态。理论科学家们根据这些化石归纳出了千年虫的一般形态特征模型，并且据此判定出千年虫就是蜈蚣的祖先！但科学家J发现了实际与理论的一些出入，他仔细的研究了上百个千年虫化石，发现其中大部分千年虫的形态都不完全符合理论模型，这到底是什么因素造成的呢？理论科学家K敏锐的指出，千年虫的形态保存在化石中很有可能发生各种变化，即便最细微的变化也能导致它不符合模型。于是，摆在科学家面前的新问题诞生了：判断一个化石中的千年虫与理论模型的差距有多大？具体来说，就是根据一个千年虫化石的形态A，找到一个符合理论模型的形态B，使 得B是最有可能在形成化石时变成形态A。
 
<img border="0" src="images/1496_1.jpg">

理论学家提出的“千年虫形态特征模型”如下（如上图所示）：躯体由头、尾、躯干、足四大部分构成。
1.头，尾用一对平行线段表示。称平行于头、尾的方向为x方向；垂直于x的方向为y方向；
2.在头尾之间有两条互不相交的折线段相连，他们与头、尾两条线段一起围成的区域称为躯干，两条折线段都满足以下条件：拐角均为钝角或者平角，且包含奇数条线段，从上往下数的奇数条垂直于x方向。
3.每条折线段从上往下数的第偶数条线段的躯干的另一侧长出一条足，即一个上、下底平行于x方向的梯形或矩形，且其中远离躯干一侧的边垂直于x方向。
注意：足不能退化成三角形（即底边的长度均大于零），躯干两侧足的数目可以不一样。（如下图，左边有4条足，右边有5条足）

<img border="0" src="images/1496_2.jpg">

可见，x-y直角坐标系内，躯干和所有足组成的实心区域的边界均平行或垂直于坐标轴。为了方便，我们假设所有这些边界的长度均为正整数。因此可以认为每个千年虫的躯体都由一些单位方格拼成。每个单位方格都由坐标(x,y)唯一确定。设头尾之间的距离为n，则我们可以用2×n个整数来描述一条千年虫B（如右图）：将B沿平行x轴方向剖分成n条宽度为1的横条，每个横条最左边一格的x坐标设为Li，最右一格的的x坐标设为Ri。则(n,L1,L2,..,Ln,R1,R2,..Rn)就确定了一条千年虫。
由于岁月的侵蚀，在实际发现的化石中，千年虫的形状并不满足上面理论模型的规则，一些格子中的躯体已经被某些矿物质溶解腐蚀了。
地质、物理、生物学家共同研究得出：
1、腐蚀是以格子为单位的，只能一整格被腐蚀；
2、腐蚀是分步进行的，每一步只有一格被腐蚀；
3、如果去掉一个格子后躯体不连通了，那么这个格子当前不会被腐蚀；
4、如果一个格子的左边邻格和右边邻格都还没被腐蚀，那么这个格子当前不会被腐蚀；
5、与头相邻的格子不能全部被腐蚀，与尾相邻的格子不能全部被腐蚀；
倘若满足上面五条，我们仍然可以用(n,L’1,L’2,..,L’n,R’1,R’2,..R’n)来描述一个化石里头的千年虫的形态。其中L’i≤R’i。
例如下图：

<img border="0" src="images/1496_3.jpg">

 

现在你的任务是，输入一个化石里的千年虫的描述A<n,L’,R’>，找一个满足理论模型的千年虫的描述B<n,L,R>，使得B可以通过腐蚀过程得以变为A，且由B转化为A的代价(须被腐蚀的格子数)最少。输出此最小代价。
</div><h2>Input</h2><div class=content>第一行为一个整数n；
以下n行，每行两个整数，其中第i行为两个整数L’i,R’i，用一个空格分开；
保证输入数据合法。
</div><h2>Output</h2><div class=content>仅一行，为一个整数，表示最少代价。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>7<br />
4 4<br />
3 4<br />
3 5<br />
1 3<br />
2 2<br />
2 4<br />
3 3<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>3<br />
</span></div><h2>HINT</h2>
			<div class=content><p><img border="0" src="images/1496_4.jpg"><br />
<br />
30%的数据  n≤100,      0≤L’i≤R’i≤100<br />
50%的数据  n≤1000,     0≤L’i≤R’i≤1000<br />
70%的数据  n≤100000,   0≤L’i≤R’i≤1000<br />
100%的数据 n≤1000000,  0≤L’i≤R’i≤1000000<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1496'>Submit</a>][<a href='problemstatus.php?id=1496'>Status</a>][<a href='bbs.php?id=1496'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
